The present invention relates to a method and apparatus for compressing digital image data.
Images are commonly stored and transmitted in digital form. Where such images include greyscale, the value of the greyscale of each pixel is provided in digital form, typically, in binary code. In images where a large range of greyscale values are required, for example, in X-rays, it is not unusual to code the greyscale levels in eight bit binary codes, thus giving 256 levels of greyscale. In general, such images are provided in raster format which comprise a plurality of horizontal scan lines, each line containing a plurality of individuals pixels, each of which is assigned a greyscale value which specifies the level of greyscale corresponding to that point in the image. Typically, the level of greyscale is defined in each pixel by an eight to twelve bit code. Because of the large number of bits which are used for defining the level of greyscale in each pixel, an image stored in raster format requires a relatively large storage capacity, and additionally, takes up a lot of bandwidth on communication channels for transmission of the image. Even in the case of a black and white image with greyscale, the storage capacity is high. In the case of colour images, where three primary colours and the corresponding intensities of the respective colours are required to define each pixel of a colour image, the storage capacity is increased by a factor of three. Various attempts have been made to compress such images, however, such attempts to date suffer from a number of disadvantages. Firstly, many compression methods are not lossless, in other words, between compression and decompression, part of the digital data making up the image is lost, and an accurate reconstruction of the image after decompression cannot be prepared. While in some applications such losses are acceptable, they are entirely unacceptable in many cases, typically, in images relating to medicine and diagnostic medicine, for example, X-rays and the like. Image compression systems which are essentially lossless suffer from the disadvantage that the compression ratio is relatively low, and thus in many cases, little saving on the storage space or the bandwidth occupied by such images in the transmission thereof is gained. Even where compression ratios are reasonable, such image compression systems tend to be relatively complex, complicated and time-consuming, and also may require large storage space to effect the compression. Typical image compression systems are described in U.S. Pat. No. 4,809,350, European Patent Specification No. 0,479,563 and European Patent Specification No. 0,536,801. The image compression methods described in these three specifications suffer from one or more of the disadvantages discussed above.
There is therefore a need for a method for compressing digital image data which overcomes the problems of known digital image data systems and which provides lossless or effectively lossless compression, while at the same time providing reasonable compression.
The present invention is directed towards providing such a method and apparatus for compressing digital image data.
The term xe2x80x9cregionxe2x80x9d as used throughout this specification and the claims means one pixel or a group of adjacent pixels.
According to the invention, there is provided a method for compressing digital image data, the method comprising the steps of
sequentially scanning a plurality of regions of the image data and determining the actual value of the data in respective regions,
predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
comparing the predicted value with the corresponding actual value of each region for which a prediction is made, and
computing the value of the difference between the respective predicted values and the corresponding actual values, and
compressing the respective difference values,
characterised in that
at least three predictions of data value are made for each region for which a prediction is being made, the predicted value which produces the median difference value of the difference values between the respective three predicted values and the actual value is selected, and the median difference value is compressed for each region for which a prediction is made, the respective predicted values for each region being based on the actual value or values of a different scanned region or regions and/or a different combination or combinations of scanned regions to those for which the others of the predictions for that region are based.
In one aspect of the invention, the digital image data is scanned region by region as a matrix array of regions.
In another aspect of the invention, one of the predictions of data value of a region for which a prediction is being made is based on the data value of the adjacent region in the column in which the region for which the prediction is being made lies.
In another aspect of the invention, one of the predictions of data value of a region for which a prediction is being made is based on the data value of the adjacent region in the row in which the region for which the prediction is being made lies.
Preferably, one of the predictions of data value of a region for which a prediction is being made is based on the gradient of data values of two regions approaching the region for which the prediction is being made. Advantageously, the prediction of the data value takes into account the slope of the gradient.
In one aspect of the invention, one of the two regions on which a prediction is based lies closer to the region for which the prediction is being made than the other of the said two regions, and the region of the said two regions which is closest to the region for which the prediction is being made is weighted.
In another aspect of the invention, one of the predictions of data value of a region for which a prediction is being made is based on the data values of three regions which are adjacent to the region for which the prediction is being made, one of the said regions lying in the same column, and the other of said regions lying in the same row as the region for which the prediction is being made, the third region being located between the said other two regions and being used for determining the gradient of the data values between the respective said other two regions and the region for which the prediction is being made.
Preferably, a prediction of the data value of every region of the digital image is made.
In one aspect of the invention, the respective median difference values are compressed by encoding the median difference values with respective variable length codes, unique codes being assigned to the respective median difference values.
Preferably, the shortest code is assigned to the most frequently occurring median difference value, and the longest code is assigned to the least frequently occurring median difference value.
Advantageously, the codes are different for the positive and negative values of the same absolute median difference values.
In one aspect of the invention, the codes assigned to the median difference values are binary codes.
Advantageously, the bit length of the longest code for the median difference values does not exceed the bit length of the data value of any region.
In one aspect of the invention, the actual data of a region is retained instead of the median difference value for that region should the median difference value for that region exceed a predetermined value. Preferably, a first flag means is set to indicate that the data following the flag means is the actual data value of the region.
In another aspect of the invention, a second flag means is set to indicate a run of actual data values where the median difference values of a run of regions exceeds a predetermined value. Preferably, the number of actual data values included in the run is associated with the second flag means. Advantageously, the second flag means is provided before the run of actual data values.
Ideally, the coded median difference values and the actual data values for the respective regions are stored in a predetermined format for subsequent retrieval and decompression.
In general, the most frequently occurring median difference value is zero.
In another aspect of the invention, noise is separated from the digital image data by separating at least the least significant bit from the value of the data in the respective regions in which a prediction of the data value is to be made, and from the adjacent regions on which the predictions are to be based prior to the prediction being made, and the separated least significant bits are stored in association with the corresponding compressed median difference values of the respective regions. Preferably, the data values remaining of the respective regions from which one or more least significant bits have been separated is divided by 2n where n is equal to the number of least significant bits separated.
Preferably, at least some of the digital image data is scanned prior to the separation of noise for determining the number of least significant bits to be separated.
In a further aspect of the invention, the digital image data is modified prior to computing the predicted data values for reducing the numerical difference between the data values occurring in the digital image data, the digital image data being modified by arranging all the determined actual data values occurring in the image data in the form of a series of actual data values in ascending order of data values, assigning each actual data value occurring in the image a modified data value so that the numerical difference between adjacent modified data values is less than the numerical difference between the respective adjacent actual data values in the series, the modified data values forming the data values on which the predictions are based. Preferably, the modified data values are assigned so that the difference between modified data values which correspond to adjacent data values in the series of data values is unity. Advantageously, the modified data values and the actual data values are cross-referenced in a look-up table. Ideally, an inverse look-up table based on the modified and the actual data values is prepared for use in subsequent reconstruction of the image.
Preferably, each look-up table is stored with the stored compressed median difference values.
In one aspect of the invention, a histogram of the actual data values occurring in the digital image data is formed for preparing each look-up table.
In one aspect of the invention, the data value of each region defines a value of greyscale between and including black and white.
In another aspect of the invention, the data value of each region defines a value of intensity of a colour in a colour image.
Ideally, the compressed data values of the digital image are stored in a predetermined format for retrieval thereof for subsequent decompression.
Ideally, each region defines a pixel. In one aspect of the invention, the digital image is in raster format.
In another aspect of the invention, the method is carried out on an acquired image after the image has been acquired.
In a further aspect of the invention, the method is carried out on an acquired image while the image is being acquired xe2x80x9con-the-flyxe2x80x9d.
In a still further aspect of the invention, the method is carried out on the acquired image with intermediate storage or in parallel with intermediate storage.
The image in compressed form is suitable for storing and/or transmission.
In another aspect of the invention, the method is used for compressing a three dimensional image, and one of the axes of the three dimensional image is time, the time axis forming a row or column of the matrix, and that row or column forming the row or column as the case may be in which a region or regions are located which form a basis for predicting a data value of a region.
In another aspect of the invention, the method further comprises the step of decompressing the compressed digital image data, the decompression method comprising the steps in reverse order to the order of the steps of the compression method.
Additionally, the invention provides a method for compressing digital image data, the method comprising the steps of
sequentially scanning a plurality of regions of the image data and determining the actual value of the data in respective regions,
predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
comparing the predicted value with the corresponding actual value of each region for which a predicted value is made, and
computing the value of the difference between the respective predicted values and the corresponding actual values, and
compressing the respective difference values,
characterised in that
the respective difference values are compressed by encoding the difference values with respective variable length codes, unique codes being assigned to the respective difference values.
Preferably, the shortest code is assigned to the most frequently occurring difference value, and the longest code is assigned to the least frequently occurring difference value.
In general, the most frequently occurring difference value is zero.
In a further aspect of the invention, the codes are different for the positive and negative values of the same absolute difference values.
The codes assigned to the difference values are binary codes.
Ideally, the bit length of the longest code does not exceed the bit length of the data value of any region.
In one aspect of the invention, the actual value of a region is retained instead of the difference value for that region should the difference value for that region exceed a predetermined value. Preferably, a first flag means is set to indicate that the data following the flag means is the actual data value of the region.
In another aspect of the invention, a second flag means is set to indicate a run of actual data values where the difference values of a run of regions exceeds a predetermined value. Preferably, the number of actual data values included in the run is associated with the second flag means. Advantageously, the second flag means is provided before the run of actual determined data values.
Ideally, the coded difference values and the actual data values for the respective regions are stored in a predetermined format for subsequent retrieval and decompression.
Further, the invention provides a method for compressing digital image data, the method comprising the steps of
sequentially scanning a plurality of regions of the image data and determining the actual value of the data in respective regions,
predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
comparing the predicted value with the corresponding actual value of each region for which a predicted value is made, and
computing the value of the difference between the respective predicted values and the corresponding actual values, and
compressing the respective difference values, characterised in that
noise is separated from the digital image data by separating at least the least significant bit from the value of the data in the respective regions in which a prediction of the data value is to be made and from the adjacent regions on which the predictions are to be based prior to the prediction being made, and
the separated least significant bits are stored in association with the corresponding compressed difference values of the respective regions.
Preferably, the data values remaining of the respective regions from which one or more least significant bits have been separated is divided by 2n where n is equal to the number of least significant bits separated.
Preferably, at least some of the digital image data is scanned prior to the separation of noise for determining the number of least significant bits to be separated.
Additionally, the invention provides a method for compressing digital image data, the method comprising the steps of
sequentially scanning a plurality of regions of the image data and determining the actual value of the data in respective regions,
predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
comparing the predicted value with the corresponding actual value of each region for which a predicted value is made, and
computing the value of the difference between the respective predicted values and the corresponding actual values, and
compressing the respective difference values,
characterised in that
the digital image data is modified prior to computing the predicted data values for reducing the numerical differences between the data values occurring in the digital image data, the digital image data being modified by arranging all the determined actual data values occurring in the image data in the form of a series of actual data values in ascending order of data values, assigning each actual data value occurring in the image a modified data value so that the numerical difference between adjacent modified data values is less than the numerical difference between the respective adjacent actual data values in the series, the modified data values forming the data values on which the predictions are based.
Preferably, the modified data values are assigned so that the difference between modified data values which correspond to adjacent data values in the series of data values is unity.
Preferably, the modified data values and the actual data values are cross-referenced in a look-up table. Advantageously, an inverse look-up table based on the modified and the actual data values is prepared for subsequent reconstruction of the image.
Ideally, each look-up table is stored with the stored compressed difference values.
In one aspect of the invention, a histogram of the actual data values occurring in the digital image data is formed for preparing the look-up tables.
Further, the invention provides apparatus for compressing digital image data, the apparatus comprising
a means for sequentially scanning a plurality of regions of the image data and for determining the actual value of the data in respective regions,
a means for predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
a means for comparing the predicted value with the corresponding actual value of each region for which a prediction is made, and
a means for computing the value of the difference between the respective predicted values and the corresponding actual values, and
a means for compressing the respective difference values,
characterised in that
the means for predicting the value of image data comprises a means for making at least three predictions of data value for each region for which a prediction is being made, a selecting means is provided for selecting the predicted data value which produces the median difference value of the difference values between the predicted data values and the actual value, and the means for compressing the respective difference values compresses the median difference values for the regions for which a prediction is made, the means for making the at least three predictions makes the respective predictions for each region based on the actual value or values of a different scanned region or regions and/or a different combination or combinations of scanned regions to those for which the others of the predictions for that region are based.
Additionally, the invention provides apparatus for compressing digital image data, the apparatus comprising the steps of
a means for sequentially scanning a plurality of regions of the image data and for determining the actual value of the data in respective regions,
a means for predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
a means for comparing the predicted value with the corresponding actual value of each region for which a prediction is made, and
a means for computing the value of the difference between the respective predicted values and the corresponding actual values, and
a means for compressing the respective difference values,
characterised in that
the means for compressing the respective difference values comprises a means for encoding the difference values with respective variable length codes, a unique code being assigned to each value of difference value.
Further, the invention provides apparatus for compressing digital image data, the apparatus comprising the steps of
a means for sequentially scanning a plurality of regions of the image data and for determining the. actual value of the data in respective regions,
a means for predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
a means for comparing the predicted value with the corresponding actual value of each region for which a prediction is made, and
a means for computing the value of the difference between the respective predicted values and the corresponding actual values, and
a means for compressing the respective difference values,
characterised in that
a means for separating noise from the digital image data is provided, the separating means separating at least the least significant bit from the value of the data in the respective regions in which a prediction of the data value is to be made, and from the adjacent regions on which the predictions are to be based prior to the prediction being made, and
a means for storing the separated least significant bits in association with the corresponding difference values of the respective regions.
The invention also provides apparatus for compressing digital image data, the apparatus comprising the steps of
a means for sequentially scanning a plurality of regions of the image data and for determining the actual value of the data in respective regions,
a means for predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
a means for comparing the predicted value with the corresponding actual value of each region for which a prediction is made, and
a means for computing the value of the difference between the respective predicted values and the corresponding actual values, and
a means for compressing the respective difference values,
characterised in that
a means is provided for modifying the digital image data prior to computing the predicted data values for reducing the numerical difference between the data values occurring in the digital image data, the said means comprising a means for arranging all the determined actual data values occurring in the image data in the form of a series of actual data values in ascending order of data values, and a means for assigning each actual data value occurring in the image a modified data value so that the numerical difference between adjacent modified data values is less than the numerical difference between the respective adjacent actual data values in the series, the modified data values forming the data values on which the predictions are based.